package queue;

import javafx.util.Pair;

import java.util.*;

public class TopKFrequent {
    public List<String> code(String[] words, int k) {
        Map<String, Integer> hash = new HashMap<>();

        for (String word : words){
            hash.put(word, hash.getOrDefault(word, 0) + 1);
        }

        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>
                (
                        (a, b) ->
                        {
                            if (a.getValue().equals(b.getValue())){
                                return b.getKey().compareTo(a.getKey());
                            }

                            return a.getValue() - b.getValue();
                        }
                );

        for (Map.Entry<String, Integer> e : hash.entrySet()){
            heap.offer(new Pair<>(e.getKey(), e.getValue()));

            if (heap.size() > k){
                heap.poll();
            }
        }

        List<String> ret = new ArrayList<>();
        while (!heap.isEmpty()){
            ret.add(heap.poll().getKey());
        }

        Collections.reverse(ret);
        return ret;
    }
}
